For consecutive image sequences such as found in video presentations, optical flow is the velocity field which warps one image into another (usually very similar) image. Optical flow is computed using the well-known optical flow equation:Ixu+Iyv+It=0  (1)where Ix, Iy, and It represent the spatio-temporal derivatives of image intensity (all known) at a given point A and (u,v) represents the (unknown) image velocity across an image sequence at the same point. The system defined by equation (1) is obviously unconstrained since at least one more constraint is required to uniquely solve for image velocity (u,v). It should be noted that equation (1) defines a line in (u,v) space, as illustrated in FIG. 5A.
A variety of methods have been employed or proposed for determining the second constraint required for unique solution of the system of equation (1). However, a common feature of the many different methods for introducing the second constraint is that the second constraint is local and heuristic. For example, one technique assumes the image velocity (u,v) is locally uniform and determines the velocity by minimizing the total error in point A by, for example, finding the image velocity (u,v) which minimizes the expression:
                              ∑          Ω                ⁢                              (                                                            I                  x                                ⁢                u                            +                                                I                  y                                ⁢                v                            +                              I                t                                      )                    2                                    (        2        )            where Ω denotes the region over which the image velocity is assumed constant. A geometric interpretation of this (least squares) minimization problem is illustrated in FIG. 5B. Basically, the vector (u,v) is found as a point with the minimum total distance from lines I1,I2,I3, . . . ,In.
The main disadvantages of this method are: (1) since the image velocity is computed for each point, the method is computationally expensive; and (2) if the image velocity or variation between sequential images is low (i.e., Ix≈Iy≈0), the image velocity either can not be determined or is very sensitive to noise. Additionally, special problems arise in the presence of strong noise and/or multiple motions present in the vicinity of image point (x,y), as illustrated in FIG. 5C.
To overcome these disadvantages, a class of methods referred to as “sparse optical flow” computation has been introduced. Such methods are typically performed utilizing two steps: (1) find points in the image with high information content (typically, high variation in Ix, Iy); and (2) compute optical flow at those points utilizing point matching between consecutive image frames (the phrases “sparse optical flow” and “point matches” will be used interchangeably herein). While these methods are faster and more reliable than “dense” optical flow methods, the disadvantage is that the optical flow is computed only at a small number of points.
There is, therefore, a need in the art for a method of combining the benefits of both dense and sparse optical flow without incurring the respective disadvantages.